package leetcode.code1130;

public class Solution {

	class Info {
		int max;
		int sum;

		public Info(int max, int sum) {
			this.max = max;
			this.sum = sum;
		}
	}

	public int mctFromLeafValues(int[] arr) {
		int len = arr.length;
		Info[][] dp = new Info[len][len];
		Info ans = f(arr, 0, len - 1, dp);
		return ans.sum;
	}

	private Info f(int[] arr, int l, int r, Info[][] dp) {
		if (l == r) {
			return new Info(arr[l], 0);
		}
		if (dp[l][r] != null) {
			return dp[l][r];
		}
		int sum = Integer.MAX_VALUE, max = 0;
		for (int i = l; i < r; i++) {
			Info left = this.f(arr, l, i, dp);
			Info right = this.f(arr, i + 1, r, dp);
			int cur = left.max * right.max + left.sum + right.sum;
			if (cur < sum) {
				sum = cur;
				max = Math.max(left.max, right.max);
			}
		}
		Info ans = new Info(max, sum);
		dp[l][r] = ans;
		return ans;
	}
}
